package com.practice.math;

/**
 * A number is supercool if it is m^n (n>=2). Given number n, find the
 * closest number which is supercool (either larger or less). (G)
 */
public class SuperCool {
	public int findSuperCool(int y) {
		if (y <= 1)
			return y;
		int superCool = 1;
		for (int i = 2;; i++) {
			int test = i * i;
			if (test - y > Math.abs(y - superCool) || test < 0)
				break;

			int t = findSuperCool(i, y);
			if (Math.abs(t - y) < Math.abs(superCool - y))
				superCool = t;
		}

		return superCool;
	}

	private int findSuperCool(int i, int y) {
		int t = 1;
		int x = y;
		while (x > 0) {
			x = x / i;
			if (x > 0)
				t *= i;
		}
		return y - t < t * i - y ? t : t * i;
	}

	/**
	 * For practice purpose, not used.
	 */
	public int pow(int x, int n) {
		int y = 1;
		int base = x;
		while (n > 0) {
			if ((n & 1) == 1)
				y *= base;
			base *= base;
			n >>= 1;
		}
		return y;
	}
}
